package com.tgy.leetcode;

import java.util.*;

/**
 * @Author: tgy
 * @Date: 12/3/20 10:51 AM
 */
public class 查找当前位置向前向后的最大值 {


    public void findPreNextMax(int[] nums) {

        if (nums == null || nums.length == 0) {

            return;
        }

        int[] locs = new int[nums.length];

        for (int i = 0; i < locs.length; i++) {

            locs[i] = -1;
        }

        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {

            while (!deque.isEmpty() && nums[deque.getFirst()] < nums[i]) {

                if (!deque.getFirst().equals(deque.getLast())) {
                    locs[deque.removeFirst()] = deque.getLast();
                }else {

                    deque.removeFirst();
                }

            }

            deque.addFirst(i);
        }

        while (!deque.isEmpty()) {

            if (!deque.getFirst().equals(deque.getLast())) {

                locs[deque.removeFirst()] = deque.getLast();
            }else {

                deque.removeFirst();
            }
        }

        System.out.println(Arrays.toString(locs));

    }
}
